1. Field of the Invention
This invention relates to an improved method and apparatus for rapidly solving Mth order linear recurrences on a data processing system using a unique linear recurrence dispersal technique. The invention can be practiced on a parallel processor or a uniprocessor or parallel processor having vector processing features.
2. Prior Art
In general, computation time for arithmetic problems in a data processing system is a function of the number of equations to be solved and the number of processors available to receive and process information. Solving an Mth order linear recurrence has heretofore been done serially where x.sub.1 is solved, then x.sub.2 is solved by plugging in x.sub.1 from the previous equation, and then solving x.sub.3 by plugging in x.sub.2, etc.
The inventor is aware of at least one attempt to solve a first order linear recurrence of length N by the Computing Research Group at the Lawrence Livermore Labs. Their technique requires approximately 1.5Nlog.sub.2 N arithmetic operations to solve the first order linear recurrence of length N, which offers a vector operation count of 3 log.sub.2 N. This method, referred to as Recursive Doubling, appears to require 0.3 log.sub.2 N times the amount of time needed to solve a first order recurrence than the time required using the linear recurrence dispersal technique disclosed herein. Wherefore, recursive doubling appears to have a greater computational requirement than the linear recurrence dispersal technique disclosed herein, rendering the linear recurrence dispersal technique the preferred alternative.